//给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
//输出：3
//解释：长度最长的公共子数组是 [3,2,1] 。
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length, nums2.length <= 1000 
// 0 <= nums1[i], nums2[i] <= 100 
// 
// Related Topics 数组 二分查找 动态规划 滑动窗口 哈希函数 滚动哈希 👍 725 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution718 {
    /**
     * 动态规划：
     * dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
     *
     * 那有同学问了，我就定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？
     *
     * 行倒是行！ 但实现起来就麻烦一点，大家看下面的dp数组状态图就明白了。
     *
     * 这里dp[i][j]定义以下标i结尾的A和以下标j结尾的B的最长重复子数组，可以看到，代码比较复杂！！！！
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength(int[] nums1, int[] nums2) {
        //dp[i][j]表示以nums1[i]和nums2[j]结尾的数组的最长子数组
        int[][] dp = new int[nums1.length][nums2.length];
        int result = 0;
        //初始化第一行
        for(int j = 0; j < nums2.length; j++){
            if(nums1[0] == nums2[j]){
                dp[0][j] = 1;
                result = 1;
            }
        }
        //初始化第一列
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                result = 1;
            }
        }

        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int result = new Solution718().findLength(new int[]{0,1,1,1,1},new int[]{1,0,1,0,1});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
